package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

//Java：从前序与中序遍历序列构造二叉树
public class ConstructBinaryTreeFromPreorderAndInorderTraversal {
    public static void main(String[] args) {
        Solution solution = new ConstructBinaryTreeFromPreorderAndInorderTraversal().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    class Solution {
        public Map<Integer, Integer> map = new HashMap<>();

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            for (int i = 0; i < inorder.length; i++) {
                map.put(inorder[i], i);
            }
            return findNodes(inorder, 0, inorder.length, preorder, 0, preorder.length);

        }

        private TreeNode findNodes(int[] inorder, int inStart, int inEnd, int[] preorder, int preStart, int preEnd) {
            if (preStart >= preEnd || inStart >= inEnd) {
                return null;
            }
            //1、前序找到根节点的值
            int rootValue = preorder[preStart];
            //2、构建根节点
            TreeNode rootNode = new TreeNode(rootValue);
            //3、找到这个节点在中序中的位置
            Integer rootIndex = map.get(rootValue);
            int offset = rootIndex - inStart;
            rootNode.left = findNodes(inorder, inStart, rootIndex, preorder, preStart + 1, preStart + 1 + offset);
            rootNode.right = findNodes(inorder, rootIndex + 1, inEnd, preorder, preStart + 1 + offset, preEnd);
            return rootNode;
        }
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}